1. Technical Field
This invention relates generally to efficient rate-based packet sending over packet switching networks. More particularly, the invention relates to a novel method to accurately generate rate-based packet sending at the rate computed by a generic congestion control algorithm. The invention addresses the issues of improving the efficiency in transporting data, audio, video and multimedia content over packet switching networks, such as the Internet, using rate-based congestion control algorithms.
2. Description of the Related Art
Packet switching networks implement a simple store-and-forward service. The most known example of packet switching network is the Internet that is built upon the Internet Protocol (IP).
Up to now, the most part of the Internet traffic is handled by the Transmission Control Protocol (TCP), which implements a congestion control protocol at the transport layer that has been extremely successful to guarantee network stability without admission control. The TCP congestion control implements a window-based protocol that sends a window ΔW(ti) of packets every time ti an acknowledgement (ACK) packet is received. This behaviour originates the bursty nature of the TCP traffic, i.e. the fact that packets are sent in bursts of length ΔW(ti). From the point of view of the network, the burstiness of the TCP increases network buffer requirements since queue sizes at least equal to the order of ΔW(ti) must be provided for efficient link utilization. Sending a burst of ΔW(ti) packets is simple to be implemented, but it is not appropriate both from the point of view of router buffers and from the point of view of users of real-time applications such as audio/video conference or live audio/video broadcast.
To reduce traffic burstiness induced by a window-based congestion control, rate-based congestion algorithms have been proposed as a valid alternative to window-based algorithms for transporting multimedia contents. With rate-based algorithms, packets are sent equally spaced in time, at interval proportional to the inverse of the sending rate.
The first solution proposed in the literature is the Rate Adaptation Protocol. (see R. Rejaie, M. Handley, D. Estrin, “RAP: An End-to-end Rate-based Congestion Control Mechanism for Realtime Streams in the Internet”, in Proc of IEEE INFOCOM '99, March 1999). In order to actuate a rate rc(t), RAP evenly spaces packets at intervals equal to the inter-packet interval (IPI) tipi computed as tipi=p/rc, where p is the packet size.
FIG. 3 shows how packets are sent: each time ti, the controller computes the rate rc(ti) and packets are sent equally spaced at intervals tipi(i)=p/rc(ti). When the computed rate changes at time ti+1 the inter-packet interval tipi(i+1) is computed accordingly.
Another rate-based congestion control is disclosed in the US patent appl. Number 20070165524 entitled “Rate based congestion control for packet networks”.
At first glance, this simple algorithm seems to be able to provide a sending rate that mitigates the burstiness. However, as it will become more clear shortly, the algorithm neglects the important feature that a general purpose OS cannot guarantee perfect timing in packet sending due to other running processes and timer granularity.
In first instance, the packet send-loop has to schedule a timer whose duration becomes smaller and smaller when the rate increases. However, timer durations are lower bounded by the OS timer granularity tg that depends on the frequency the CPU scheduler is invoked. By noting that in current Operating Systems typical values for tg are in the order of 1-10 ms, the maximum achievable rate is given by rmax=p/tg, which means that a timer granularity as low as 1 ms and a packet size p=1500B, turns out a maximum rate of 12 Mbps.
In second instance, the sending rate produced by packet gap-based algorithms is not accurate due to the fact that timers are not precise in a general purpose OS. As an example, the popular Symbian operating system, that is one of the leading OS for mobile phones, supports timers whose minimum duration is equal to 1/64 of second, resulting in an error that can be as high as 15.625 ms.
Let us take a closer look at the way the CPU scheduler assigns processes to the CPU. When a process is running, but the CPU is not assigned to it, the process is said to be in the wait queue. The amount of time a process spends in the wait queue before obtaining again the CPU is defined as waiting time tw≧0 and it depends on the CPU load. For this reason, if a process schedules a sleep timer whose nominal duration is t seconds, the process will be actually assigned again to the CPU after t+tw seconds.
Therefore, the actual packet sending rate produced by the packet send loop is affected by the OS load, which acts as a disturbance. In particular, the effective rate is
      p                  t        _            +              t        w              ,which is less than the computed rate
      r    c    =            p              t        _              .  FIG. 4 shows perfect timing, i.e. one packet is sent exactly every tipi(i) (i.e. tw≡0), and actual timing, i.e. each packet is sent with a delay tw, which turns out an effective rate
      p                  t        ipi                  (          i          )                    +              t        w              <                    r        c            ⁡              (                  t          k                )              .  
In general, the sending rate rc(ti) can be computed synchronously, f.i. every round trip time (RTT), or asynchronously every time a feedback report (or ACK) packet is received from network nodes or from the receiver. Feedbacks can be implicit, such as timeouts or duplicate acknowledgements (DUPACKs), or explicit such as Explicit Congestion Notification (ECN).
Another approach addressing the issue of implementing a rate-based congestion control is presented in RFC 3448 where a send loop is proposed to implement the rate-based TCP Friendly Rate Control (TFRC) algorithm.
The algorithm is based on that employed by RAP, but it considers for the first time the uncertainty of the inter-packet intervals tipi due to the fact that the send loop process shares the CPU with other processes. In particular, RFC 3448 tries to counteract the effect of imprecise timer duration by sending a packet without waiting for all the inter packet interval in the case this interval has elapsed except that for an amount equal to Δ computed as
      Δ    =          min      ⁡              (                                            t              ipi                        2                    ,                                    t              g                        2                          )              ,where tg is the operating system scheduler granularity. We interpret this design choice as a heuristic aiming at anticipating the packet sending time to compensate when the sending times are delayed due to imprecise timers.
Even though such a mechanism seems to be able to efficiently solve the issue of rate-based data sending, the produced (or actuated) rate does not match the desired one computed by the congestion control algorithm.
In fact, even though TFRC is going through the IETF standardization process since January 2003, the Master Thesis by A. Saurin (see Alvaro Saurin, “Congestion Control for Video-conferencing Applications”, MSc Thesis, University of Glasgow, December 2006), advised by Prof. Colin Perkins (University of Glasgow), shows that the mechanism described in RFC 3448 is not able to efficiently and precisely generate the sending rate computed by a rate-based congestion control algorithm.
For these considerations, the implementation of a rate-based congestion control algorithm is an open issue at this time.
When window-based congestion control algorithms are used, packet pacing is a packet sending technique that can be employed in order to approximate a rate-based behaviour. Basically, packet pacing applied to window-based congestion control mechanisms such as the Transmission Control Protocol (TCP), consists in sending a window worth of packets by adequately spacing them in order to provide a rate-based packet sending.
In fact, it is well-known that TCP sends new packets when an acknowledgement (ACK) packet is received, i.e. TCP is ack-clocked. In particular, on ACK reception the TCP congestion control algorithm sends an amount of packets equal to:ΔW=cwnd−outstandingwhere cwnd is the congestion window and outstanding represents the number of in flight packets, i.e. the number of un-acknowledged packets.
When the amount of data ΔW to be sent is large, the performances of the congestion control mechanism are affected as much as the router buffers are small. When the packet pacing mechanism is employed, the number of packets ΔW is not immediately sent as a whole on ACK reception, but it is sent one packet at a time by adequately spacing the packets. It worth noting that the amount of data ΔW must be sent in at most RTT seconds, otherwise the average rate generated by employing packet pacing technique would be less than the one achieved by window-based sending. For this reason, in order to evaluate the correct temporal duration of inter-packet gaps, an estimate of the value of the current round trip time is needed.
To summarize, packet pacing techniques applied to window-based congestion control mechanism rely on timers in order to schedule packet sending as in the case of rate-based algorithms, thus experiencing all the problems we have described above.